package sort;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author XY
 * @version 1.0
 * @date 2022/2/16 9:08
 * @Description
 */
public class Leet1356 {
    public static int[] sortByBits(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length-i-1; j++) {
                String s = Integer.toBinaryString(arr[j]);
                String length1 = s.replaceAll("1", "");
                int i1 = s.length() - length1.length();
                String s1 = Integer.toBinaryString(arr[j+1]);
                String length2 = s1.replaceAll("1", "");
                int i2 = s1.length() - length2.length();
                if(i1>i2){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }else if(i1==i2){
                    if(arr[j]>arr[j+1]){
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
            }
        }

        return arr;
    }

    public static int[] sortByBits2(int[] arr){
        //Integer.bitCount(i)的返回值是i的二进制表示中1的个数
        List<Integer> collect = Arrays.stream(arr).boxed().sorted(Comparator.comparing(Integer::bitCount).thenComparing(o -> o)).collect(Collectors.toList());
        int[] res = new int[arr.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = collect.get(i);
        }
        return res;
    }

    public int[] sortByBits1(int[] arr) {

        int[] bit = new int[10001];
        List<Integer> list = new ArrayList<Integer>();
        for (int x : arr) {
            list.add(x);
            bit[x] = get(x);
        }

        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer x, Integer y) {
                if (bit[x] != bit[y]) {
                    return bit[x] - bit[y];
                } else {
                    return x - y;
                }
            }
        });
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    public int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 2;
            x /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1024,512,256,128,64,32,16,8,4,2,1};
        int[] ints = sortByBits2(arr);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
}
